// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>

int const inf = 1 << 28;
int const maxn = 20007;
int top[maxn];
int tid[maxn];
int id[maxn];
int size[maxn];
int depth[maxn];
int parent[maxn];
int heavy_son[maxn];

int end_point[maxn];
int next[maxn];
int head[maxn];
int weight[maxn];
int edge_alloc;

int cost[maxn];
int n, dfs_tick;

void init()
{
	edge_alloc = 2;
	std::memset(head, 0, sizeof(head));
}

void add_edge(int u, int v, int c)
{
	end_point[edge_alloc] = v; weight[edge_alloc] = c; next[edge_alloc] = head[u]; head[u] = edge_alloc++;
	end_point[edge_alloc] = u; weight[edge_alloc] = c; next[edge_alloc] = head[v]; head[v] = edge_alloc++;
}


int seg_max[4 * maxn];
int seg_min[4 * maxn];
int color[4 * maxn];

void push_down(int id)
{
	int tl = id * 2, tr = tl ^ 1;
	color[tl] ^= 1;
	color[tr] ^= 1;
	color[id] = 0;
}

void push_up(int id)
{
	int tl = id * 2, tr = tl ^ 1;
	int tmax = -inf, tmin = inf;
	if (color[tl]) {
		  tmax = std::max(tmax, -seg_min[tl]);
		  tmin = std::min(tmin, -seg_max[tl]);
	} else {
		tmax = std::max(tmax, seg_max[tl]);
		tmin = std::min(tmin, seg_min[tl]);
	}
	if (color[tr]) {
		  tmax = std::max(tmax, -seg_min[tr]);
		  tmin = std::min(tmin, -seg_max[tr]);
	} else {
		tmax = std::max(tmax, seg_max[tr]);
		tmin = std::min(tmin, seg_min[tr]);
	}
	seg_max[id] = tmax;
	seg_min[id] = tmin;
}

void seg_interval_max_update(int id, int l, int r, int x, int y, int val)
{
	if (x <= l && r <= y) { seg_min[id] = seg_max[id] = val; color[id] = 0; return; }
	if (color[id]) push_down(id);
	int tl = id * 2, tr = tl ^ 1, mid = (l + r) / 2;
	if (x <= mid) seg_interval_max_update(tl, l, mid, x, y, val);
	if (mid < y) seg_interval_max_update(tr, mid + 1, r, x, y, val);
	push_up(id);
}

void update(int id, int val)
{
	int u = end_point[id], v = end_point[id ^ 1];
	if (parent[u] == v) std::swap(u, v);
	seg_interval_max_update(1, 1, n, tid[v], tid[v], val);
}

void seg_negate(int id, int l, int r, int x, int y)
{
//	std::cout << id << ' ' << l << ' ' << r << ' ' << x << ' ' << y << '\n';
	if (x <= l && r <= y) { color[id] ^= 1; return; }

	if (color[id]) push_down(id);
	int tl = id * 2, tr = tl ^ 1, mid = (l + r) / 2;
	if (x <= mid) seg_negate(tl, l, mid, x, y);
	if (mid < y) seg_negate(tr, mid + 1, r, x, y);
	push_up(id);
}

int seg_query(int id, int l, int r, int x, int y)
{
	if (x <= l && r <= y) {
		if (color[id]) return -seg_min[id];
		return seg_max[id];
	}
	if (color[id]) push_down(id);
	int tl = id * 2, tr = tl + 1, mid = (l + r) / 2, ret = -inf;
	if (x <= mid) ret = std::max(ret, seg_query(tl, l, mid, x, y));
	if (mid < y) ret = std::max(ret, seg_query(tr, mid + 1, r, x, y));
	push_up(id);
	return ret;
}

int query(int u, int v)
{
	int ret = -inf;
	while (top[u] != top[v]) {
		if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
		ret = std::max(ret, seg_query(1, 1, n, tid[top[u]], tid[u]));
		u = parent[top[u]];
	}
	if (depth[u] > depth[v]) std::swap(u, v);
	ret = std::max(ret, seg_query(1, 1, n, tid[u] + 1, tid[v]));
	return ret;
}

void negate(int u, int v)
{
	while (top[u] != top[v]) {
		if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
		seg_negate(1, 1, n, tid[top[u]], tid[u]);
		u = parent[top[u]];
	}
	if (depth[u] > depth[v]) std::swap(u, v);
	seg_negate(1, 1, n, tid[u] + 1, tid[v]);
}

void dfs_size(int u, int p, int d)
{
	parent[u] = p;
	depth[u] = d;
	size[u] = 1;
	heavy_son[u] = 0;
	int max_size = 0;
	for (int i = head[u]; i; i = next[i]) {
		int v = end_point[i];
		if (v == p) continue;
		cost[v] = weight[i];
		dfs_size(v, u, d + 1);
		size[u] += size[v];
		if (size[v] > max_size) {
			max_size = size[v];
			heavy_son[u] = v;
		}
	}
}

void dfs_heavy_chain(int u, int ancestor)
{
	tid[u] = ++dfs_tick;
	top[u] = ancestor;
	seg_interval_max_update(1, 1, n, tid[u], tid[u], cost[u]);
	if (heavy_son[u]) dfs_heavy_chain(heavy_son[u], ancestor);
	for (int i = head[u]; i; i = next[i]) {
		int v = end_point[i];
		if (v == parent[u] || v == heavy_son[u]) continue;
		dfs_heavy_chain(v, v);
	}
}

int main()
{
	int T;
	std::scanf("%d", &T);
	while (T--) {
		std::scanf("%d", &n);
		init();
		for (int i = 1, x, y, c; i < n; i++) {
			std::scanf("%d %d %d", &x, &y, &c);
			id[i] = edge_alloc;
			add_edge(x, y, c);
		}

		dfs_size(1, 0, 0);

		//std::fill(seg_min, seg_min + 4 * maxn, inf);
		//std::fill(seg_max, seg_max + 4 * maxn, -inf);
		std::memset(seg_min, 0, sizeof(seg_min));
		std::memset(seg_max, 0, sizeof(seg_max));
		std::memset(color, 0, sizeof(color));
		cost[1] = -inf;
		dfs_tick = 0;
		dfs_heavy_chain(1, 1);

		char s[10];
		while (std::scanf("%s", s) && s[0] != 'D') {
			int x, y;
			std::scanf("%d %d", &x, &y);
			if (s[0] == 'C')
				update(id[x], y);
			else if (s[0] == 'Q')
				std::printf("%d\n", query(x, y));
			else
				negate(x, y);
		}
	}
}

